package array;

import java.util.HashSet;
import java.util.Set;

public class 寻找文件副本 {
    //暴力
    class Solution {
        public int findRepeatDocument(int[] documents) {
            for(int i=0;i<documents.length;i++){
                for(int j=i+1;j<documents.length;j++){
                    if(documents[i]==documents[j])
                        return documents[i];
                }
            }
            return -1;
        }
    }
    //哈希
    class Solution2 {
        public int findRepeatDocument(int[] documents) {
            Set<Integer> hash = new HashSet<>();
            for(int i : documents){
                if(hash.contains(i))
                    return i;
                hash.add(i);
                System.out.println(documents[i]);
            }
            return -1;
        }
    }
    //原地交换
    class Solution3 {
        public int findRepeatDocument(int[] documents) {
            int i = 0;
            while (i < documents.length){
                if(i == documents[i]){
                    i++;
                    continue;
                }
                if(documents[documents[i]] == documents[i])
                    return documents[i];
                int tmp = documents[i];
                documents[i] = documents[tmp];
                documents[tmp] = tmp;
            }
            return -1;
        }
    }

}
